COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002				Reliable Algorithms
C00011 00003	An algorithm need not work with numbers. Here is an algorithm to find a word in
C00016 ENDMK
C⊗;
			Reliable Algorithms

			  Robert W. Floyd
			  Copyright  1983

There is a traditional algorithm used by Russian peasants to multiply numbers
of several digits, based on doubling, halving, and addition.  To see why it
works, let's first look at a particular multiplication problem.

How much is 38 x 45?  Since 38 = 19 x 2, 38 x 45 = 19 x 2 x 45 = 19 x 90.  
That's 90 more than 18 x 90, so

	19 x 90 = 18 x 90 + 90 = 9 x 2 x 90 + 90 = 9 x 180 + 90

Since 9 x 180 is 180 more than 8 x 180,

	9 x 180 + 90  = 8 x 180 + 180 + 90 = 8 x 180 + 270

		      = 4 x 2 x 180 + 270 = 4 x 360 + 270

	4 x 360 + 270 = 2 x 2 x 360 + 270 = 2 x 720 + 270 = 1440 + 270 = 1710.

Now that the method is clear, the process can be shortened to filling out a table.
In each row, we have two numbers we want to multiply, and another number to be
added on to the result.  For the calculation above, here is the table:

		A	B	C

	       38      45	 0
	       19      90	 0
	       18      90       90
		9     180	90
		8     180      270
		4     360      270
		2     720      270
		1    1440      270
		0    1440     1710

Here is an explicit algorithm for making the table.

(1) The first row across contains, in columns A and B, the numbers we want to
    multiply, 38 and 45 in this example, and in column C a zero.

(2) If A=0 in the bottom row of the table, we are finished; the entry in column C
    is the answer.  Otherwise we need to make another row.  

(3) If A is even in the bottom row, we make the next row by halving the number
    in column A, doubling the number in column B, and copying the previous number
    from column C.

(4) If A is odd in the bottom row, we make the next row by subtracting one from
    the number is column A, copying the member in column B, and adding the number 
    from column B to the number in column C.

Every row in the table stands for a formula; the fifth row, above, stands for
8 x 180 + 270.  People who work with algorithms find ways to represent entities
that are not just numbers by sequences of numbers; this allows using computers
that only handle numbers to solve problems that involve not only numbers, but
pictures, words, formulas, logic, and myriad others.

The successive rows represent different formulas, but each formula stands for
the same number as the one before it, so they all stand for the same number.
We get from the problem to the solution by picking a first line that is easy
to construct from the problem, and getting to a last line from which it is easy
to construct the solution.  In between, we need steps that are easy to carry
out, that progress toward an acceptable last line, and that change the question
without changing the answer.  That is, we go from ``What is 8 x 180 + 270?'' to
``What is 4 x 360 + 270?'' without changing the answer, 1710.

A good algorithm is like good government; it involves both stability and progress.
Progress in solving a problem comes from changing it into a simpler problem;
stability comes from assuring that each new problem has the same answer as the one
it grew from.  In the Russian peasant multiplication algorithm, progress is
quaranteed because columnn A gets closer to zero at every step; it can't go on
forever, since there are only a limited number of possible values A can have,
once we know the first value.  Stability is guaranteed because in each row, the
formula AxB+C has the same value.

A similar algorithm, known to Euclid around 430 B.C., finds the largest number
that evenly divides two given numbers.  If we want to reduce a fraction like
385/315 to its simplest form, we find 35 as the greatest common divisor (g.c.d.)
of 385 and 315, and say 385/315 = (385/35)/(315/35) = 11/9.  We can get greatest
common divisors by trial and error, but there is a much more efficient way.
Here is a table given by Euclid's algorithm finding the g.c.d. of 385 and 3l5:

		A	B

	       315     385
	       315      70
		70     315
		70     245
		70     175
		70	35
		35	70
		35	35

The algorithm sets up the first row with the smaller number in column A, and
the larger in column B.  As long as B is bigger than A, it makes the next row
by copying A, and reducing B by A (subtraction).  If B gets smaller than A, it
makes the next row by exchanging A with B.  If B is equal to A in a row, that
number is the greatest common divisor.

The principle of stability is that the common divisors of A and B are the same
in each row.  In this example, in every row both A and B are multiples of
1,5,7, and 35.  If we decrease B by A, the result is still a multiple of
1,5,7, and 35, but no new common divisors are introduced (a little easy algebra
will convince you).

The principle of progress can be formulated in several ways.  One way is that
the value of 2A+B decreases at every step, while staying positive.

A more efficient formulation of Euclid's algorithm uses remainders (of division)
rather than subtraction.  Here it finds the g.c.d. of 315 and 385 again:

		A	B

	       315     385
		70     315
		35	70
		 0	35

As before, in the first line A is the smaller datum, B the larger.  When we get
to a line with A=0, we stop, and B is the answer.  Otherwie, we find the
remainder when B is divided by A.  In the next line, A is that remainder, while 
B is copied from A in this line.

In the improved version of the algorithm, the principle of stability is the same;
all the rows have the same common divisors and therefore the same g.c.d.  The
principle of progress is that A decreases at every step, without becoming negative. 
An algorithm need not work with numbers. Here is an algorithm to find a word in
the dictionary.

Insert your left index finger between pages at the beginning of the dictionary,
and your right index finger at the end.  Open the dictionary somewhere between
your fingers (If you can't, you've already found the right page).  Look at the
word in the top left corner of the newly opened page.  If it is alphabetically
earlier than the word you are looking for, move your left index finger into the
new opening; otherwise, move your right index finger there.  Here is a record of
my looking up ``scutage'' in the Shorter Oxford English Dictionary.

	Left finger		Right finger		New opening

     page number  word	     page number   word	     page number  word

	   1	A		2475	Zygin		1278	Monthly
    	1278	Monthly		2475	Zygin		1822	Sea-horse
	1278	Monthly		1822	Sea-horse	1542	Pomatum
	1542	Pomatum		1822	Sea-horse	1682	Redowa
	1682	Redowa		l822	Sea-horse	1730	Revolutionary
	1730	Revolutionary   1822	Sea-horse	1780	Sailyard
	1780    Sailyard	1822	Sea-horse	1800	Scantity
	1800	Scantity	1822	Sea-horse	1810	Scorer
	1810	Scorer		1822	Sea-horse	1816	Scriptural
	1816	Scriptural	1822	Sea-horse	1820	Sea
	1816	Sciptural	1822	Sea-horse	1818	Sculptile
	1818	Sculptile	1820	Sea		(none)

The principle of stability is that the word I'm looking for stays between my
fingers.  The principle of progress is that the number of pages between my
fingers gets smaller.

Many algorithms embodied in computer programs are not reliable; when used on
certain data they give wrong answers, or they continue calculating until
someone intervenes.  The way to make an algorithm reliable is to design it
around a principle of stability and a principle of progress.  If you can't
formulate a principle of stability for an algorithm, it is likely to change
the problem it is solving as it goes along, and end up computing the right
answer to the wrong problem.  If you can't formulate a principle of progress,
the algorithm is likely to run forever on some data.  As the Russian peasant
multiplication and greatest common divisor algorithms show, it becomes much
easier to understand a new algorithm when its principle of stability (technically
known as an invariant) is presented with it.